package pri.zjy.tree;

import pri.zjy.tree.model.NTreeNode;

import java.util.List;

/**
 * @author zhangjy
 * @description N 叉树的最大深度
 * @date 2025/4/11 11:23
 */
public class MaxDepth_559 {

    // bfs-层序遍历解法没什么区别，跳过；

    /**
     * 个解-dfs-递归-后序，转化为求高度
     */
    public int maxDepth3(NTreeNode root) {
        if (root == null) return 0;

        // 所有孩子向下递归
        List<NTreeNode> children = root.children;
        // 当前节点的最大深度
        int maxChildDepth = 0;
        for (NTreeNode child : children) {
            // 左、右；每个孩子的最大深度
            int childDepth = maxDepth(child);
            // 中；所有孩子的最大深度
            maxChildDepth = Math.max(maxChildDepth, childDepth);
        }
        return maxChildDepth + 1;
    }

    /**
     * 个解-dfs-递归-先序；
     * 自上而下，统计最大深度。
     * 初始变量不同。
     */
    private int maxDepth2 = 0;
    public int maxDepth2(NTreeNode root) {
        dfs2(root, 0);
        return maxDepth2;
    }

    public void dfs2(NTreeNode node, int depth) {
        if (node == null) return;

        // 先++，再记录，是因为maxDepth、depth初始都为0，要把当前层记录上
        depth++;
        // 记录本层的最大深度
        maxDepth2 = Math.max(maxDepth2, depth);

        // 所有孩子向下递归
        List<NTreeNode> children = node.children;
        for (NTreeNode child : children) {
            dfs(child, depth);
        }

    }

    /**
     * 个解-dfs-递归-先序；
     * 自上而下，统计最大深度。
     */
    private int maxDepth = 1;
    public int maxDepth(NTreeNode root) {
        if (root == null) return 0;

        dfs(root, 1);
        return maxDepth;
    }

    public void dfs(NTreeNode node, int depth) {
        if (node == null) return;

        // 记录本层的最大深度
        maxDepth = Math.max(maxDepth, depth);
        depth++;

        // 所有孩子向下递归
        List<NTreeNode> children = node.children;
        for (NTreeNode child : children) {
            dfs(child, depth);
        }

    }



}
